from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        dp = [1, 0, 0, 0]
        for num in nums:
            if num == 0:
                dp[1] = dp[1] * 2 + dp[0]
                dp[1] %= MOD
            elif num == 1:
                dp[2] = dp[2] * 2 + dp[1]
                dp[2] %= MOD
            else:
                dp[3] = dp[3] * 2 + dp[2]
                dp[3] %= MOD
            # print(dp)
        return dp[3]


if __name__ == "__main__":
    print(Solution().countSpecialSubsequences([0, 1, 2, 2]))  # 3
    print(Solution().countSpecialSubsequences([2, 2, 0, 0]))  # 0
    print(Solution().countSpecialSubsequences([0, 1, 2, 0, 1, 2]))  # 7
    print(Solution().countSpecialSubsequences([2, 0, 0, 2, 0, 1, 2]))  # 7
